﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm.Middle_1361_ValidateBinaryTreeNodes
{
    public class TreeModel
    {
        public int value;
        public TreeModel left;
        public TreeModel right;

        public TreeModel(int value, TreeModel left = null, TreeModel right = null)
        {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
    public class TreeModel1
    {
        public int index;
        public int value;
        public int count;

        public TreeModel1(int index, int value)
        {
            this.index = index;
            this.value = value;
            if (this.value == -1) this.count = -1;
            else this.count = 1;
        }
    }

    class MainProject
    {
        static void Main(string[] args)
        {
            //int[] nums1 = new int[] { 1, -1, 3, -1 };
            //int[] nums2 = new int[] { 2, -1, -1, -1 };
            //int[] nums1 = new int[] { 1, 0 };
            ////int[] nums2 = new int[] { -1, -1 };
            //int[] nums1 = new int[] { 1, -1, -1, 4, -1, -1 };
            //int[] nums2 = new int[] { 2, -1, -1, 5, -1, -1 };
            //int[] nums1 = new int[] { 3, -1, 1, -1 };
            //int[] nums2 = new int[] { -1, -1, 0, -1 };
            int[] nums1 = new int[] { 1, 0, 3, -1 };
            int[] nums2 = new int[] { -1, -1, -1, -1 };
            //int[] nums1 = new int[] { 1, -1, 3, -1 };
            //int[] nums2 = new int[] {2, 3, -1, -1 };
            Console.WriteLine(ValidateBinaryTreeNodes2(4, nums1, nums2));

            Console.ReadKey();
        }

        #region 查找根节点+BFS
        public static bool ValidateBinaryTreeNodes2(int n, int[] leftChild, int[] rightChild)
        {
            int root = -1;
            List<int> allNums = new List<int>();
            for (int i = 0; i < leftChild.Length; i++)
            {
                if (leftChild[i] != -1)
                {
                    if (!allNums.Contains(leftChild[i]))
                    {
                        allNums.Add(leftChild[i]);
                    }
                    else
                    {
                        return false;
                    }
                }
            }
            for (int i = 0; i < rightChild.Length; i++)
            {
                if (rightChild[i] != -1)
                {
                    if (!allNums.Contains(rightChild[i]))
                    {
                        allNums.Add(rightChild[i]);
                    }
                    else
                    {
                        return false;
                    }

                }
            }
            if (n - allNums.Count != 1)
            {
                return false;
            }
            for (int i = 0; i < n; i++)
            {
                if (allNums.Contains(i))
                    allNums.Remove(i);
                else
                    root = i;

            }
           
            Console.WriteLine("root = {0}", root);

            Queue<int> que = new Queue<int>();
            HashSet<int> hash = new HashSet<int>();
            int length = 0;
            que.Enqueue(root);
            while (que.Count > 0)
            {
                int size = que.Count;
                for (int i = 0; i < size; i++)
                {
                    int value = que.Dequeue();
                    if (hash.Add(value))
                    {
                        length++;
                        if (leftChild[value] != -1)
                        {
                            que.Enqueue(leftChild[value]);
                        }
                        if (rightChild[value] != -1)
                        {
                            que.Enqueue(rightChild[value]);
                        }
                    }
                    else
                    {
                        return false;
                    }
                }
            }
            if (length==n)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        #endregion

        #region 方法二 超时了(暴力解法一般都会超时)
        public static TreeModel IsContain(int value, List<TreeModel> allNode)
        {
            TreeModel isExit = null;
            allNode.ForEach(i =>
            {
                if (i.value == value)
                {
                    isExit = i;
                }
            });
            return isExit;
        }

        public static bool ValidateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild)
        {
            List<TreeModel> allNode = new List<TreeModel>();
            List<int> allNums = new List<int>();
            List<int> allNums2 = new List<int>();
            for (int i = 0; i < n; i++)
                allNums.Add(i);
            for (int i = 0; i < n; i++)
                allNums2.Add(i);
            //思路：还原二叉树，最后遍历（简答思考可行）排除法获取根节点
            for (int i = 0; i < n; i++)
            {
                TreeModel treeModel1 = IsContain(i, allNode);
                if (treeModel1 == null)
                {
                    treeModel1 = new TreeModel(i);
                    allNode.Add(treeModel1);
                    if (leftChild[i] != -1)
                    {
                        TreeModel treeModel2 = IsContain(leftChild[i], allNode);
                        if (treeModel2 == null)
                        {
                            treeModel1.left = new TreeModel(leftChild[i]);
                            allNums.Remove(leftChild[i]);
                            allNode.Add(treeModel1.left);
                        }
                        else
                        {
                            treeModel1.left = treeModel2;
                            allNums.Remove(treeModel2.value);
                        }
                    }
                    if (rightChild[i] != -1)
                    {
                        TreeModel treeModel2 = IsContain(rightChild[i], allNode);
                        if (treeModel2 == null)
                        {
                            treeModel1.right = new TreeModel(rightChild[i]);
                            allNums.Remove(rightChild[i]);
                            allNode.Add(treeModel1.right);
                        }
                        else
                        {
                            treeModel1.right = treeModel2;
                            allNums.Remove(treeModel2.value);
                        }
                    }
                }
                else
                {
                    if (leftChild[i] != -1)
                    {
                        TreeModel treeModel2 = IsContain(leftChild[i], allNode);
                        if (treeModel2 == null)
                        {
                            treeModel1.left = new TreeModel(leftChild[i]);
                            allNums.Remove(leftChild[i]);
                            allNode.Add(treeModel1.left);
                        }
                        else
                        {
                            treeModel1.left = treeModel2;
                            allNums.Remove(treeModel2.value);
                        }
                    }
                    if (rightChild[i] != -1)
                    {
                        TreeModel treeModel2 = IsContain(rightChild[i], allNode);
                        if (treeModel2 == null)
                        {
                            treeModel1.right = new TreeModel(rightChild[i]);
                            allNums.Remove(rightChild[i]);
                            allNode.Add(treeModel1.right);
                        }
                        else
                        {
                            treeModel1.right = treeModel2;
                            allNums.Remove(treeModel2.value);
                        }
                    }
                }
            }
            if (allNums.Count == 1)
            {
                TreeModel root = IsContain(allNums[0], allNode);
                if (root != null)
                {
                    return Middle(root, allNums2) == false ? false : (allNums2.Count == 0 ? true : false);
                }
                else
                {
                    return false;
                }
            }
            else
            {
                return false;
            }
        }

        public static bool Middle(TreeModel treeModel, List<int> allNums)
        {
            if (treeModel == null)
                return true; ;

            if (allNums.Contains(treeModel.value))
            {
                allNums.Remove(treeModel.value);
                Console.WriteLine(treeModel.value);
            }
            else
            {
                return false;
            }

            return Middle(treeModel.left, allNums) && Middle(treeModel.right, allNums);
        }
        #endregion
        /// <summary>
        /// 题目意思理解偏差
        /// </summary>
        /// <param name="n"></param>
        /// <param name="leftChild"></param>
        /// <param name="rightChild"></param>
        /// <returns></returns>
        public static bool ValidateBinaryTreeNodes1(int n, int[] leftChild, int[] rightChild)
        {
            List<TreeModel1> left = new List<TreeModel1>();
            List<TreeModel1> right = new List<TreeModel1>();

            for (int i = 0; i < leftChild.Length; i++)
            {
                left.Add(new TreeModel1(i, leftChild[i]));
            }

            for (int i = 0; i < rightChild.Length; i++)
            {
                right.Add(new TreeModel1(i, rightChild[i]));
            }

            List<int> list = new List<int>();
            for (int i = 1; i < n; i++)
            {
                list.Add(i);
            }
            bool res = Validate(0, n, left, right, list);
            if (list.Count > 0) return false;

            return res;
        }

        public static bool Validate(int id, int n, List<TreeModel1> left, List<TreeModel1> right, List<int> list)
        {
            if (id == -1) return true;

            TreeModel1 leftValue = left[id];
            if (leftValue.value == -1)
            {
            }
            else
            {
                if (leftValue.count >= 1)
                {
                    if (list.Contains(leftValue.value))
                    {
                        list.Remove(leftValue.value);
                        leftValue.count--;
                    }
                    else
                    {
                        return false;
                    }
                }
                else
                    return false;
            }

            TreeModel1 rigthValue = right[id];
            if (rigthValue.value == -1)
            {
            }
            else
            {
                if (list.Contains(rigthValue.value))
                {
                    list.Remove(rigthValue.value);
                    rigthValue.count--;
                }
                else
                {
                    return false;
                }
                //if (rigthValue.count >= 1)
                //    rigthValue.count--;
                //else
                //    return false;
            }

            return Validate(leftValue.value, n, left, right, list) && Validate(rigthValue.value, n, left, right, list);

        }
    }
}
